{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Breaking Hardware ECC on CW305 FPGA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Background\n",
    "To get the most out of this tutorial, some basic knowledge of elliptic curves, and in particular of point multiplication on elliptic curves, is required. A good overview is available here: https://cryptojedi.org/peter/data/eccss-20130911b.pdf.\n",
    "\n",
    "The side-channel attack presented here targets the scalar multiplier (\"k\") in the elliptic curve point multiplication. Point multiplication is the most expensive operation in many (if not all?) cryptographic uses of elliptic curves. The secret scalar is not the private key, but learning the scalar used in an ECDSA signature (for example) allows the secret key to be trivially calculated.\n",
    "\n",
    "This attack is quite different from the AES side-channel attacks in our other tutorials. In most ECC point multiplication implementations (including the target used here), the secret scalar k is consumed one bit at a time. At a high level, the attack is very simple:\n",
    "1. Identify when each bit of k is processed on the power trace.\n",
    "2. Find how processing a '1' is different from processing a '0'.\n",
    "3. Assemble the secret k, one bit at a time.\n",
    "\n",
    "Since we are attacking k one bit at a time, its size has no impact on the difficulty of the attack. The curve used in this attack is the NIST P-256 curve; the same approach would work just as well with a larger curve.\n",
    "\n",
    "Our attack requires multiple traces to be collected. The secret k remains constant for each trace, but a different point must be used for each trace. However, we require no knowledge whatsoever of what the points actually are. Furthermore, if the attacker is limited to collecting a single trace for a given value of k, we will show in the end that we can correctly guess most of k.\n",
    "\n",
    "The target for this attack is the point multiplication submodule of the [Cryptech ecdsa256 core](https://wiki.cryptech.is/log/user/shatov/ecdsa256).\n",
    "Refer to the README in your ChipWhisperer repository (`firmware/fpgas/cryptosrc/cryptech/ecdsa256/README.md`) for details on the target and the modifications that were made to it for this attack."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Series Overview\n",
    "\n",
    "This tutorial is the first part of a 5-part series. In this tutorial, we develop a basic attack and demonstrate its viability.\n",
    "\n",
    "Part 2 improves the attack and introduces new ways to measure its performance.\n",
    "\n",
    "In part 3, we switch from the attacker chair to the defender chair: we propose and evaluate several countermeasures to resist our attack.\n",
    "\n",
    "In part 4, we study one more countermeasure which yields new insights on the target's leakage.\n",
    "\n",
    "Part 5 concludes by looking at what TVLA can tell us about the target's leakage, with the benefit of all that we learned in the previous sections.\n",
    "\n",
    "If you only do part 1, you'll learn quite a bit about hardware ECC and how it may be attacked, and you could choose to stop there. Hopefully you'll find this sufficiently interesting to cover the remaining sections and learn even more!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Capture Notes\n",
    "\n",
    "Most of the capture settings used below are similar to the standard ChipWhisperer scope settings. Some important points to note:\n",
    "\n",
    "- The full ECC operation takes over one million clock cycles, so it is best done with a ChipWhisperer-Pro or Husky.\n",
    "- With a ChipWhisperer-Lite, every trace needs to be captured in several steps, using the sample offset feature (47 steps to be precise!), so trace acquisition is much slower: around 5 seconds/trace, versus 4 traces/second with the CW-Pro or Husky. Be patient! Luckily, the attack doesn't require a large number of traces.\n",
    "- It's possible that better results would be obtained with x4 sampling, but that would make trace acquisition with the CW-Lite *very* slow.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Supported Setups\n",
    "\n",
    "This tutorial requires a CW305 or CW312T-A35 target, and either a CW-Lite (two-part), CW-Pro or CW-Husky.\n",
    "\n",
    "The tutorial was developed with a CW-Pro and the CW305 100t FPGA; the observations made in the attack's development will be accurate if you're using the same, but other combinations of capture and target hardware can diverge and may require some modifications to the attack code.\n",
    "\n",
    "The same holds if you re-build the FPGA bitfile.\n",
    "\n",
    "#### CW312T_A35 notes:\n",
    "- More traces may be required for the attacks to succeed.\n",
    "- Some of the observations with respect to the efficacy of countermeasures (in parts 3 onwards) won't line up exactly with what you observe.\n",
    "- The CW312T_A35-specific settings that are used assume the use of the inductive shunt; if you're using a different shunt, some tweaks will be required.\n",
    "\n",
    "#### CW-Lite notes:\n",
    "- Your results may not correspond exactly to the notebook's comments, especially in the first attempt when using the power measured on specific clock cycles. This is likely due to the 5x higher clock frequency being used, which is done to keep the trace acquisition time reasonable.\n",
    "- You may need to adjust the suggested threshold values.\n",
    "- In the end, the final attack works well with the CW-lite, although it tends to require a few more traces.\n",
    "\n",
    "If you don't have hardware, you can still follow along using the provided pre-recorded traces (set `TRACES` to `\"SIMULATED\"`). Because this is ECC and traces are so large (the full target operation takes 1.2 million cycles), most saved traces are not full traces of the ECC operation; they are segmented traces (chopped up subsets of full traces, keeping only the parts needed for the attack). Additionally, many of the results shown in this series of notebooks are also presented in the [Ark of the ECC eprint paper](https://eprint.iacr.org/2021/1520.pdf).\n",
    "\n",
    "Pre-recorded traces were obtained with `CWHUSKY` and `CW305_100t`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#PLATFORM = 'CWLITE'\n",
    "#PLATFORM = 'CWPRO'\n",
    "PLATFORM = 'CWHUSKY'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TARGET_PLATFORM = 'CW305_100t'\n",
    "#TARGET_PLATFORM = 'CW305_35t'\n",
    "#TARGET_PLATFORM = 'CW312T_A35'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TRACES = 'HARDWARE' # if you have the required capture+target hardware: capture actual traces\n",
    "#TRACES = 'SIMULATED' # if you don't have capture+target hardware: use pre-captured traces (these traces were obtained using CW-Husky with a  CW305_100t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer as cw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Capture Setup\n",
    "\n",
    "Setup is somewhat similar to other targets. This time, however, we'll be using an external clock (from the FPGA). We'll also do the rest of the setup manually.\n",
    "\n",
    "If you're using pre-recorded traces, skip ahead to the \"Trace Capture\" section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scope = cw.scope()\n",
    "scope.default_setup()\n",
    "scope.adc.offset = 0\n",
    "scope.adc.basic_mode = \"rising_edge\"\n",
    "scope.trigger.triggers = \"tio4\"\n",
    "scope.io.tio1 = \"serial_rx\"\n",
    "scope.io.tio2 = \"serial_tx\"\n",
    "scope.io.hs2 = \"disabled\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we'll connect to the CW305 board. Here we'll need to specify our bitstream file to load as well as the usual scope and target_type arguments.\n",
    "\n",
    "Pick the correct bitfile for your target board with the TARGET_PLATFORM variable. By setting `force=False`, the bitfile will only be programmed if the FPGA is uninitialized (e.g. after powering up). Change to `force=True` to always program the FPGA (e.g. if you have generated a new bitfile).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    scope.io.hs2 = 'clkgen'\n",
    "    fpga_id = 'cw312t_a35'\n",
    "    platform = 'ss2'\n",
    "else:\n",
    "    scope.io.hs2 = \"disabled\"\n",
    "    platform = 'cw305'\n",
    "    if TARGET_PLATFORM == 'CW305_100t':\n",
    "        fpga_id = '100t'\n",
    "    elif TARGET_PLATFORM == 'CW305_35t':\n",
    "        fpga_id = '35t'\n",
    "\n",
    "target = cw.target(scope, cw.targets.CW305_ECC, force=True, fpga_id=fpga_id, platform=platform)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the CW-Pro, each trace can be captured in one go with streaming mode. However this requires the target clock to be no more than 10 MHz.\n",
    "\n",
    "The CW-Husky can also capture a full trace in streaming mode. It's able to stream faster so we use a 15 MHz clock.\n",
    "\n",
    "With the CW-Lite, we can only capture 24.4K samples at a time, but on the other hand we can increase the target clock up to 50 MHz, which speeds up the capture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if PLATFORM == 'CWPRO':\n",
    "    scope.adc.stream_mode = True\n",
    "    scope.adc.samples = 1200000\n",
    "    target.pll.pll_outfreq_set(10E6, 1)\n",
    "    target._clksleeptime = 150\n",
    "    scope.gain.db = 20\n",
    "elif PLATFORM == 'CWHUSKY':\n",
    "    scope.adc.stream_mode = True\n",
    "    scope.adc.samples = 1200000\n",
    "    target.pll.pll_outfreq_set(15E6, 1)\n",
    "    target._clksleeptime = 100\n",
    "    scope.gain.db = 20\n",
    "elif PLATFORM == 'CWLITE':\n",
    "    scope.adc.samples = 24400\n",
    "    target.pll.pll_outfreq_set(50E6, 1)\n",
    "    target._clksleeptime = 30\n",
    "    scope.gain.db = 30"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you're using the CW312T-A35 target, the clock needs to be set to 7.37 MHz (because of the target's baud rate):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    scope.clock.clkgen_freq = 7.37e6\n",
    "    scope.io.hs2 = 'clkgen'\n",
    "    scope.gain.db = 35\n",
    "    if PLATFORM == 'CWHUSKY':\n",
    "        scope.clock.clkgen_src = 'system'\n",
    "        scope.clock.adc_mul = 1\n",
    "        scope.clock.reset_dcms()\n",
    "    else:\n",
    "        scope.clock.adc_src = \"clkgen_x1\"\n",
    "    import time\n",
    "    time.sleep(0.1)\n",
    "    target._ss2_test_echo()\n",
    "    \n",
    "else:\n",
    "    if PLATFORM == 'CWHUSKY':\n",
    "        scope.clock.clkgen_freq = 15e6\n",
    "        scope.clock.clkgen_src = 'extclk'\n",
    "        scope.clock.adc_mul = 1\n",
    "    else:\n",
    "        scope.clock.adc_src = \"extclk_x1\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Husky's ADC has higher latency that CW-Pro's and CW-Lite's, which means that the collected power samples are offset. In this attack, we look at the power consumed on precise clock cycles. In order to reference the same clock cycles for all capture hardware, we use the trigger offset feature to account for the different latency:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if PLATFORM == 'CWHUSKY':\n",
    "    scope.adc.offset = 3\n",
    "else:\n",
    "    scope.adc.offset = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we set all the PLLs. We enable CW305's PLL1; this clock will feed both the target and the CW ADC. As explained [here](http://wiki.newae.com/Tutorial_CW305-1_Building_a_Project#Capture_Setup), **make sure the DIP switches on the CW305 board are set as follows**:\n",
    "- J16 = 0\n",
    "- K16 = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 'CW305' in TARGET_PLATFORM:\n",
    "    target.vccint_set(1.0)\n",
    "    # we only need PLL1:\n",
    "    target.pll.pll_enable_set(True)\n",
    "    target.pll.pll_outenable_set(False, 0)\n",
    "    target.pll.pll_outenable_set(True, 1)\n",
    "    target.pll.pll_outenable_set(False, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ensure ADC is locked:\n",
    "scope.clock.reset_adc()\n",
    "assert (scope.clock.adc_locked), \"ADC failed to lock\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Occasionally the ADC will fail to lock on the first try; when that happens, the above assertion will fail (and on the CW-Lite, the red LED will be on). Simply re-running the above cell again should fix things."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trace Capture\n",
    "Below is the capture loop. The main body of the loop loads some new multiplication parameters, arms the scope, then finally records and appends our new trace to the `traces[]` list.\n",
    "\n",
    "Note that the multiplication result is read from the target and compared to the expected results, as a sanity check."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First let's pick a scalar for which we can very easily distinguish ones from zeros. Remember that k is the secret that we want to be able to retrieve with our side-channel attack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 0xffffffffffffffffffffffffffffffff00000000000000000000000000000000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook contains a bunch of methods that we'll use frequently, including a trace capture method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run \"CW305_ECC_setup.ipynb\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We just need a single trace to start with. The `full=True` argument specifies that the full power trace should be captured:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "traces = get_traces(1, k, 'part1_1', full=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Buidling the Attack: Trace Analysis\n",
    "\n",
    "In the following, we build up the attack from scratch. In this way, while we are developing an attack which is very specific to our target, we show the methods you would use to build an attack for a different target.\n",
    "\n",
    "Let's start by looking at a single trace. Let's start with the first 20k cycles only (you can plot the full trace but that will be very slow because it's a long trace!)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bokeh.plotting import figure, show\n",
    "from bokeh.resources import INLINE\n",
    "from bokeh.io import output_notebook\n",
    "\n",
    "output_notebook(INLINE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = figure(width=2000)\n",
    "\n",
    "samples = 20000\n",
    "#samples = len(traces[0].wave)\n",
    "xrange = list(range(samples))\n",
    "p.line(xrange, traces[0].wave[:samples], line_color=\"red\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There seems to be a very strong periodicity to the trace. We can confirm this by simulating the target core and looking at what it's actually doing.\n",
    "\n",
    "If you want to go through the whole process, install the [iverilog simulator](http://iverilog.icarus.com/) (Ubuntu: `apt-get install iverilog`) and follow along below; otherwise skip ahead to the next section, **\"Finding Ones and Zeros\"**.\n",
    "\n",
    "The next step runs the simulation and takes several minutes; you can see that it's still alive by looking at the `make.log` file. Once it's done, you'll see its output here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%bash\n",
    "cd ../../../firmware/fpgas/ecc/sim/\n",
    "make DUMP=1 WAVEFORMAT=vcd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This produces a simulation waveform `../../../firmware/fpgas/ecc/sim/results/tb.fst` which you can look at with gtkwave.\n",
    "\n",
    "What we're going to do is record at what times the multiplication core's internal `bit_counter` changes, which tells us when the core is processing which bit of the secret k scalar.\n",
    "\n",
    "We can automatically extract these event times with the vcdvcd package (https://github.com/cirosantilli/vcdvcd). Unfortunately this step needs to ingest the full 2.7G file all at once, so it's also very slow (again if you're impatient you can skip ahead to the next section)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from vcdvcd import VCDVCD\n",
    "vcd = VCDVCD('../../../firmware/fpgas/ecc/sim//results/tb.fst')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've ingested the simulation waveform, extracting event times from it is almost instantaneous:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kbittimes = vcd['tb.U_dut.U_curve_mul_256.bit_counter[7:0]']\n",
    "cyclecounts = vcd['tb.cycle_count[31:0]']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With a bit of Python magic we build up the `cycles` array, which contains the clock cycle number for when each bit of k is processed, relative to the start of the point multiplication operation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cycles = []\n",
    "deltas = []\n",
    "for i in range(1,257):\n",
    "    cycles.append(int(cyclecounts[kbittimes.tv[i][0]],2))\n",
    "    if (i > 1):\n",
    "        deltas.append(cycles[-1] - cycles[-2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One thing we can see right away is that each bit takes *exactly* 4204 cycles to process. So, no timing attacks here: the operation is rock-solid time-constant.\n",
    "\n",
    "Go ahead and try with different values of k and P if you want; don't bother with the lengthy waveform generation and extraction, just look at the `trace.textout['cycles']` attribute to see how many clock cycles the job took (as measured by the scope looking at the target's trigger signal)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "min(deltas), max(deltas)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "traces[0].textout['cycles']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We only need to do this lengthy step once, so let's save the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import os\n",
    "\n",
    "cycles_file = 'data/ecc_cycles.npy'\n",
    "# avoid overwriting:\n",
    "if not os.path.exists(cycles_file):\n",
    "    numpy.save(cycles_file, cycles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding Ones and Zeros:\n",
    "\n",
    "The previously saved `cycles.npy` tells us at which clock cycle the target core is processing each bit of k. If you skipped over the previous section, carry on from here.\n",
    "\n",
    "We begin by loading the array which tells us on which clock cycle processing begins for every bit of k:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "cycles = np.load('data/ecc_cycles.npy')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's overlay the power trace from a few differents bits of k, including both ones and zeros:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "r = figure(width=2000)\n",
    "\n",
    "samples = 4204\n",
    "xrange = list(range(samples))\n",
    "for i, color in zip([10, 20, 30, 200, 210, 220], ['red', 'green', 'blue', 'orange', 'purple', 'brown']):\n",
    "    r.line(xrange, traces[0].wave[cycles[i]:cycles[i]+samples], line_color=color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The peaks line up *perfectly*, and the different bits appear indistinguishable.\n",
    "\n",
    "Of course, side-channel attacks work by picking up the smallest of differences, so we're not done yet...\n",
    "\n",
    "Our next step is to average the power trace for all k=1 bits and all k=0 bits **from a single multiplication trace** to see if we can spot any differences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# pick any trace here:\n",
    "trace = traces[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "avg_trace = np.zeros(samples)\n",
    "\n",
    "for start in cycles[1:]:\n",
    "    avg_trace += trace.wave[start:start+samples]\n",
    "\n",
    "avg_trace /= len(cycles[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "avg_ones = np.zeros(samples)\n",
    "\n",
    "for start in cycles[1:128]:\n",
    "    avg_ones += trace.wave[start:start+samples]\n",
    "\n",
    "avg_ones /= 128"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "avg_zeros = np.zeros(samples)\n",
    "\n",
    "for start in cycles[128:256]:\n",
    "    avg_zeros += trace.wave[start:start+samples]\n",
    "\n",
    "avg_zeros /= 128"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = figure(width=2000)\n",
    "\n",
    "xrange = list(range(len(avg_trace)))\n",
    "#s.line(xrange, avg_ones, line_color=\"red\")\n",
    "#s.line(xrange, avg_zeros, line_color=\"blue\")\n",
    "s.line(xrange, avg_ones - avg_zeros, line_color=\"orange\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bingo!** We see substantial differences at the very start and very end of the bit processing. Zoom in around cycle 4202 to quantify the difference; it's not big, but it's there.\n",
    "\n",
    "Now, remember that the difference we've found here is from the average of 128 measurements.\n",
    "\n",
    "The question is: is the difference seen in the average consistently present for *individual* bits of k. Let's look at that with some interactive plotting.\n",
    "\n",
    "First let's define a helper function to sum the power samples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sums(no_traces):\n",
    "    sums = []\n",
    "    # in case samples were recorded as ints, translate result to make it as though they were floats\n",
    "    if 'int' in str(type(traces[0].wave[0])):\n",
    "        shift = True\n",
    "        if PLATFORM != 'CWHUSKY':\n",
    "            center = 2**9\n",
    "            div = 2**10\n",
    "        # infer whether trace was collected with 8 or 12 bits per sample:\n",
    "        elif max(abs(traces[0].wave)) > 255:\n",
    "            center = 2**11\n",
    "            div = 2**12\n",
    "        else:\n",
    "            center = 2**7\n",
    "            div = 2**8\n",
    "    else:\n",
    "        shift = False\n",
    "\n",
    "    if len(traces[0].wave) >= 1130000:\n",
    "        # full captures\n",
    "        for c in cycles:\n",
    "            sum = 0\n",
    "            for trace in traces[:no_traces]:\n",
    "                for i in poi:\n",
    "                    power = trace.wave[c+abs(i)]\n",
    "                    if shift:\n",
    "                        power = (power - center)/div\n",
    "                    if i < 0:\n",
    "                        sum -= power\n",
    "                    else:\n",
    "                        sum += power\n",
    "            sums.append(sum)\n",
    "    else:\n",
    "        # segmented captures (used for pre-captured traces, to save space)\n",
    "        segment_size = len(traces[0].wave) // SEGMENTS\n",
    "        for c in range(256):\n",
    "            sum = 0\n",
    "            for trace in traces[:no_traces]:\n",
    "                for i in poi:\n",
    "                    # complicated mapping to deal with the segmented traces\n",
    "                    if abs(i) > segment_size:\n",
    "                        absi = segment_size - (SEGMENT_CYCLES - abs(i))\n",
    "                    else:\n",
    "                        absi = abs(i)\n",
    "                    if i < 0:\n",
    "                        i = -absi\n",
    "                    else:\n",
    "                        i = absi\n",
    "                    index = c*segment_size+abs(i) + cycles[0]\n",
    "                    power = trace.wave[index]\n",
    "                    if shift:\n",
    "                        power = (power - center)/div\n",
    "                    if i < 0:\n",
    "                        sum -= power\n",
    "                    else:\n",
    "                        sum += power\n",
    "            sums.append(sum)\n",
    "    return sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `poi` array contains the clock cycles for which we sum the power measurement.\n",
    "\n",
    "For positive numbers, `get_sums()` adds the power measurement at that clock cycle; for negative numbers, `get_sums()` substracts the power measurement at abs(clock cycle).\n",
    "\n",
    "The `poi` defined here was chosen for the CW-Pro + CW305-100T combination; **some other combinations may require different indices to obtain good results**!\n",
    "\n",
    "The earlier plot which shows the difference between average one's and average zero's should guide you to choose the proper points for your setup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    poi = [4202, -4203, 7, -8]\n",
    "else:\n",
    "    poi = [4202, -6, 7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we acquire more traces. Here we specify `full=False` in order to capture only the segments of the power trace that we need for our analysis and attack.\n",
    "\n",
    "This is only supported by CW-Husky; if you're using CW-Pro or CW-Lite, you'll have to change this argument to `False`. The analysis code will automatically how to index into the power trace for both cases, so you need not worry about that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "traces = get_traces(30, k, 'part1_2', full=False, samples_per_segment=64, as_int=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you get a number of warnings stating that the operation too more clock cycles than expected (typically 1 more clock cycle), you may get slightly different results from what's described in this notebook (due to some samples being off by 1).\n",
    "You should be able to resolve the issue by resetting the ADC DCM (`scope.clock.reset_adc()`) or restarting the notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's set up an interactive plot which lets us see whether we can distinguish k bits that are ones from k bits that are zeros, and how many traces might be required to do so reliably:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_plot(no_traces):\n",
    "    SS.data_source.data['y'] = get_sums(no_traces)\n",
    "    push_notebook()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ipywidgets import interact, Layout\n",
    "from bokeh.io import push_notebook\n",
    "\n",
    "no_traces = 15\n",
    "S = figure(width=2000)\n",
    "\n",
    "xrange = list(range(len(cycles)))\n",
    "sums = get_sums(no_traces)\n",
    "SS = S.line(xrange, sums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(S, notebook_handle=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "interact(update_plot, no_traces=(1, len(traces)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The x-axis of this plot is the index of the k bit being processed by the target; the y-axis is the metric which we hope to use to distinguish ones from zeros. The metric we used here is the sum of the power measurements at cycles 6, 7 and 4202.\n",
    "\n",
    "Recall that our secret scalar k was set to {128 ones, 128 zeros}. So if our distinguishing metric is good, we expect the first half of the plot to be distinguishable from the second half.\n",
    "\n",
    "With a single trace, the results aren't great: the two halves are statistically different, but an attacker wouldn't be able to correctly guess all k bits.\n",
    "\n",
    "But by the time the slider hits about 8 traces, the two halves no longer overlap. With over 15 traces, the two halves are very distinct. We may have a successful side-channel attack!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sanity check\n",
    "\n",
    "Before we declare victory, let's check whether our 0/1 distinguisher still works when k is **not** made of very long strings of 0's and 1's:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 0xffffffffffffffff0000000000000000aaaa0000cccc00001111000033330000\n",
    "traces = get_traces(50, k, 'part1_3', full=False, samples_per_segment=64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bokeh.models import Label\n",
    "S2 = figure(width=2000)\n",
    "#poi = [4202, -6, 7]\n",
    "xrange = list(range(len(cycles)))\n",
    "sums = get_sums(len(traces))\n",
    "SS = S2.line(xrange, sums)\n",
    "\n",
    "if PLATFORM == 'CWPRO':\n",
    "    shift = 6\n",
    "elif PLATFORM == 'CWLITE':\n",
    "    shift = -4\n",
    "else:\n",
    "    shift = 0\n",
    "\n",
    "mytext_AAAA = Label(x=130, y=6+shift, text='0xAAAA')\n",
    "mytext_CCCC = Label(x=160, y=7+shift, text='0xCCCC')\n",
    "mytext_1111 = Label(x=195, y=6+shift, text='0x1111')\n",
    "mytext_3333 = Label(x=230, y=7+shift, text='0x3333')\n",
    "\n",
    "S2.add_layout(mytext_AAAA)\n",
    "S2.add_layout(mytext_CCCC)\n",
    "S2.add_layout(mytext_1111)\n",
    "S2.add_layout(mytext_3333)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(S2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Uh-oh**: when the k bits alternate between 0 and 1 every bit (e.g. bits 128-143), it looks like we get a constant metric that's about halfway between what we get for long strings of ones and long strings of zeros (e.g. bit 0-63 and 64-127).\n",
    "\n",
    "Let's plot some components of our metric separately:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S3 = figure(width=2000)\n",
    "\n",
    "no_traces = len(traces)\n",
    "\n",
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    pois = [-4203, 7]\n",
    "else:\n",
    "    pois = [4202, 7]\n",
    "\n",
    "poi = [pois[0]]\n",
    "sums = np.asarray(get_sums(no_traces)) + 4    # just a vertical shift for easier visualization \n",
    "S4202 = S3.line(xrange, sums, line_color='red')\n",
    "\n",
    "poi = [pois[1]]\n",
    "sums = np.asarray(get_sums(no_traces)) - 2\n",
    "S7 = S3.line(xrange, sums, line_color='blue')\n",
    "\n",
    "mytext_AAAA = Label(x=130, y=4, text='0xAAAA')\n",
    "mytext_CCCC = Label(x=160, y=4, text='0xCCCC')\n",
    "mytext_1111 = Label(x=195, y=4, text='0x1111')\n",
    "mytext_3333 = Label(x=230, y=4, text='0x3333')\n",
    "\n",
    "S3.add_layout(mytext_AAAA)\n",
    "S3.add_layout(mytext_CCCC)\n",
    "S3.add_layout(mytext_1111)\n",
    "S3.add_layout(mytext_3333)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(S3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ah-ha!** At bits 128-143, we see that the red curve is offset from the blue curve by one cycle, so when k changes every bit, the changes tend to cancel each other out.\n",
    "\n",
    "This plot also shows that the red curve appears to have a better signal-to-noise ratio. It also has a more regular behaviour at the very beginning.\n",
    "\n",
    "Maybe we can proceed with this attack by using only the power measurement at cycle 4202."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### One more thing...\n",
    "\n",
    "But what about those peaks seen in the first few cycles?\n",
    "\n",
    "Let's do another sanity check, this time with k not starting with a long string of ones:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 0x0000ffffffffffff0000000000000000aaaa0000cccc00001111000033330000\n",
    "traces = get_traces(30, k, 'part1_4', full=False, samples_per_segment=530) # using more samples here because we'll need them for the correlation attack later"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S4 = figure(width=2000)\n",
    "\n",
    "no_traces = len(traces)\n",
    "\n",
    "poi = [pois[0]]\n",
    "sums = np.asarray(get_sums(no_traces)) + 2    # just a vertical shift for easier visualization \n",
    "S4202 = S4.line(xrange, sums, line_color='red')\n",
    "\n",
    "poi = [pois[1]]\n",
    "sums = np.asarray(get_sums(no_traces)) - 2\n",
    "S7 = S4.line(xrange, sums, line_color='blue')\n",
    "\n",
    "leading_zeros = Label(x=0, y=2.75, text='leading zeros')\n",
    "first_one = Label(x=17, y=4.25, text='first one')\n",
    "ones = Label(x=20, y=2, text='0xFFF...')\n",
    "zeros = Label(x=70, y=1, text='0x000...')\n",
    "\n",
    "\n",
    "S4.add_layout(leading_zeros)\n",
    "S4.add_layout(first_one)\n",
    "S4.add_layout(ones)\n",
    "S4.add_layout(zeros)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(S4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normally, zeros get the lowest score, but when they are at the beginning of k, they get the highest score with cycle 4202; the behaviour with cycles 6 and 7 is stranger still.\n",
    "\n",
    "This is getting a bit messy: having to distinguish between 3 levels will require a higher SNR. Also, if you repeat the above test with `k=0x1000...`, `k=0x3000...` and similar values, you'll see that it harder still to properly identify those first few bits.\n",
    "\n",
    "We're **really** close to a working attack. In fact we could pretty much stop here: we can identify most bits of k, we just have some trouble with the first few; if we omit the unlikely cases where k starts with a very long string of zeros, we could simply and quickly brute force those first few bits.\n",
    "\n",
    "But let's try something else (promise, this one's going to work): a slightly different approach which will give a cleaner attack, and which will also give us some insight into **why** the leakage is happening.\n",
    "\n",
    "If you're a hardware designer, then what follows may be the most instructive part of this tutorial."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ...To the Verilog!\n",
    "\n",
    "If you're not too scared of a little Verilog, run the Verilog simulation as shown earlier in the notebook and open the simulation waveform in gtkwave. (If you are scared, just skip over to the **\"Correlation Attack\"** section.)\n",
    "\n",
    "Then bring up `./firmware/fpgas/cryptosrc/cryptech/ecdsa256/rtl/curve/curve_mul_256.v` in a text editor.\n",
    "\n",
    "Follow the `k_din` input. This is our secret k that we wish to retrieve with the side-channel attack.\n",
    "\n",
    "`k_din` gets loaded into `k_din_reg`, and its most significant bit is assigned to `move_inhibit`, which in turns goes to `copy_t2r_int`. This last signal is used to enable the writing of intermediate results to the `bram_1rw_1ro_readfirst` memory instances. There are 3 such memories; one for each of the x, y, and z point coordinates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cryptograpy Detour\n",
    "\n",
    "To progress from here, a little bit of elliptic curve knowledge is required.\n",
    "\n",
    "You may have noticed that the point that the target core is tasked to multiply is given with $(x,y)$ coordinates. Why is there a $z$ coordinate now in the source code? Without fully reversing the implementation, it's safe to assume that the target takes the given point from its *affine* $(x,y)$ coordinates and transforms it into *projective* $(x,y,z)$ coordinates. Many (most?) ECC implementations do this because point multiplication is faster in projective coordinates (https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates gives a good overview of this).\n",
    "\n",
    "Now let's load that simulation waveform and look at the write timing on those `bram_1rw_1ro_readfirst` instances by probing `bram_rx_wr_en`, `bram_ry_wr_en` and `bram_rz_wr_en`. If you stare at it for a few minutes you should recognize that the write timings are *identical* for every bit of k, except for the last set of writes which are blocked whenever `move_inhibit` is high.\n",
    "\n",
    "We can now make a pretty safe guess that the multiplication algorithm used is **double and always add**. Point multiplication in general consists of repeated doublings and adds. In this implementation, for each bit of k, the intermediate result goes through a point doubling and a point add; the result of the point add is discarded if the addition is not required, which is dependent on the value of the k bit being processed. `move_inhibit` is the logic which controls this discarding. This multiplication algorithm is a simple way to achieve time-constant execution, and, depending on implementation details, make it harder for side-channel attacks to identify whether the secret bit being processed is a 1 or a 0.\n",
    "\n",
    "We now have a decent (and hopefully correct!) understanding of the implementation. For the purpose of side-channel attacks, we are now reasonably certain that the target does *exactly* the same thing independent of k, *except* for the storage operation which is masked via `move_inhibit`, depending on k.\n",
    "\n",
    "The set of 8 writes that are blocked by `move_inhibit` occur on clock cycles 4195 to 4203 (relative to the processing of each bit of k). *Hmm,* 4195-4203... do these numbers sound familiar? Recall that 4202 is the clock cycle where we noted a statistical difference between processing a 1 versus a 0!\n",
    "\n",
    "We know from our first attempt that looking at only the last set of writes doesn't lead to a clean attack. But now that we understand what's happening at those clock cycles, we can try something else to leverage the leakage that we've found. On the simulation waveform, we can look at the next time that the `bram_1rw_1ro_readfirst` memory instances are read (after the possibly blocked memory write). Here's the idea: if `move_inhibit` was not set, then the next memory read will return what was written at cycles 4195-4203; otherwise, it will return something else. The correlation between the power samples at those two points in time might be able to tell us whether `move_inhibit` was set or not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Correlation Attack\n",
    "\n",
    "First let's define the cycle offsets where the memory read and writes that we're interested in are occurring.\n",
    "\n",
    "The x/y/z writes happen simultaneously (at cycle `rupdate_offset`), but the three coordinates are read at three different times (`r[x|y|z]read_offset`).\n",
    "\n",
    "The correlation is computed over `rupdate_cycles = 8` clock cycles, because that's how many clock cycles it takes to read or write an intermediate $R_x$, $R_y$ or $R_z$ value (256-bit values into 32-bit wide memories)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rupdate_offset = 4195\n",
    "rupdate_cycles = 8\n",
    "rxread_offset = 205\n",
    "ryread_offset = 473\n",
    "rzread_offset = 17\n",
    "\n",
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    rupdate_cycles += 8\n",
    "    rupdate_offset -= 4\n",
    "    rxread_offset -= 4\n",
    "    ryread_offset -= 4\n",
    "    rzread_offset -= 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we compute the correlations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = len(traces)\n",
    "corrsxonly = []\n",
    "corrsyonly = []\n",
    "corrszonly = []\n",
    "\n",
    "segment_size = len(traces[0].wave) // SEGMENTS\n",
    "\n",
    "for i in range (0, len(cycles)-1):\n",
    "    corrx = 0\n",
    "    corry = 0\n",
    "    corrz = 0\n",
    "\n",
    "    if len(traces[0].wave) >= 1130000:\n",
    "        start1 = cycles[i] + rupdate_offset\n",
    "        stop1  = cycles[i] + rupdate_offset + rupdate_cycles\n",
    "\n",
    "        start2x = cycles[i+1] + rxread_offset\n",
    "        start2y = cycles[i+1] + ryread_offset\n",
    "        start2z = cycles[i+1] + rzread_offset\n",
    "\n",
    "        stop2x  = cycles[i+1] + rxread_offset + rupdate_cycles\n",
    "        stop2y  = cycles[i+1] + ryread_offset + rupdate_cycles\n",
    "        stop2z  = cycles[i+1] + rzread_offset + rupdate_cycles\n",
    "\n",
    "    else:\n",
    "        start1 = cycles[0] + (i+1)*segment_size - (SEGMENT_CYCLES - rupdate_offset)\n",
    "        stop1  = cycles[0] + (i+1)*segment_size - (SEGMENT_CYCLES - rupdate_offset) + rupdate_cycles\n",
    "\n",
    "        start2x = cycles[0] + (i+1)*segment_size + rxread_offset\n",
    "        start2y = cycles[0] + (i+1)*segment_size + ryread_offset\n",
    "        start2z = cycles[0] + (i+1)*segment_size + rzread_offset\n",
    "\n",
    "        stop2x  = cycles[0] + (i+1)*segment_size + rxread_offset + rupdate_cycles\n",
    "        stop2y  = cycles[0] + (i+1)*segment_size + ryread_offset + rupdate_cycles\n",
    "        stop2z  = cycles[0] + (i+1)*segment_size + rzread_offset + rupdate_cycles\n",
    "\n",
    "\n",
    "    for trace in traces[:t]:\n",
    "        corrx += np.corrcoef(trace.wave[start1:stop1], trace.wave[start2x:stop2x])[0][1]\n",
    "        corry += np.corrcoef(trace.wave[start1:stop1], trace.wave[start2y:stop2y])[0][1]\n",
    "        corrz += np.corrcoef(trace.wave[start1:stop1], trace.wave[start2z:stop2z])[0][1]\n",
    "\n",
    "    corrsxonly.append(corrx/t)\n",
    "    corrsyonly.append(corry/t)\n",
    "    corrszonly.append(corrz/t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C = figure(width=2000)\n",
    "\n",
    "xrange = list(range(len(corrsyonly)))\n",
    "\n",
    "#C.line(xrange, corrsxonly, line_color=\"orange\")\n",
    "C.line(xrange, corrsyonly, line_color=\"purple\", line_width=3)\n",
    "#C.line(xrange, corrszonly, line_color=\"brown\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We appear to have good results with 30 traces! The correlation with the y-coordinate read is very good; the x-coordinate read has a strange peak at the start that we don't want to deal with, as well as a lower SNR, and the z-coordinate read appears to have no correlation whatsoever.\n",
    "\n",
    "For the attack, we'll use correlation from the y-coordinate read only.\n",
    "\n",
    "This image below illustrates illustrates how to define the thresholds that we'll use to identify ones and zeros. When $k$ starts with a leading zero, the correlations scores behave differently until the first one is encountered, so we use two thresholds to decide whether each bit is a one or a zero.\n",
    "\n",
    "If you're not using a CW-Pro and CW305, your own result may look different, and you may need the thresholds that are defined below.\n",
    "\n",
    "![Thresholds](img/ECC_threshold.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Attack\n",
    "\n",
    "Finally: here is the attack in full. We start by repeating the trace acquisition, this time with a non-trivial value for k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 0x70a12c2db16845ed56ff68cfc21a472b3f04d7d6851bf6349f2d7d5b3452b38a\n",
    "#k = random_k()\n",
    "traces = get_traces(40, k, 'part1_5', full=False, samples_per_segment=530)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll repeat some previous cells that are needed here, so that you don't have to run through the whole notebook in order for this to work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm.notebook import trange\n",
    "import numpy as np\n",
    "import time\n",
    "cycles = np.load('data/ecc_cycles.npy')\n",
    "rupdate_offset = 4195\n",
    "rupdate_cycles = 8\n",
    "ryread_offset = 473\n",
    "\n",
    "if TARGET_PLATFORM == 'CW312T_A35':\n",
    "    rupdate_cycles += 8\n",
    "    rupdate_offset -= 4\n",
    "    ryread_offset -= 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the decision thresholds:\n",
    "\n",
    "If these parameters don't work for you, go back up to the last plot before this section and pick appropriate thresholds based on what you see on your own plot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if PLATFORM == 'CWPRO':\n",
    "    initial_threshold = -0.02\n",
    "    regular_threshold = 0\n",
    "elif PLATFORM == 'CWLITE':\n",
    "    initial_threshold = -0.38\n",
    "    regular_threshold = -0.23\n",
    "elif PLATFORM == 'CWHUSKY':\n",
    "    if TARGET_PLATFORM == 'CW312T_A35':\n",
    "        initial_threshold = -0.15\n",
    "        regular_threshold = -0.2\n",
    "    else:\n",
    "        initial_threshold = -0.35\n",
    "        regular_threshold = -0.40"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute the correlations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "corrs = []\n",
    "attack_traces = len(traces)\n",
    "#attack_traces = 5\n",
    "\n",
    "for i in range (0, len(cycles)-1):\n",
    "    corr = 0\n",
    "    if len(traces[0].wave) >= 1130000:\n",
    "        start1 = cycles[i] + rupdate_offset\n",
    "        stop1  = cycles[i] + rupdate_offset + rupdate_cycles\n",
    "        start2y = cycles[i+1] + ryread_offset\n",
    "        stop2y  = cycles[i+1] + ryread_offset + rupdate_cycles\n",
    "    else:\n",
    "        start1 = cycles[0] + (i+1)*segment_size - (SEGMENT_CYCLES - rupdate_offset)\n",
    "        stop1  = cycles[0] + (i+1)*segment_size - (SEGMENT_CYCLES - rupdate_offset) + rupdate_cycles\n",
    "        start2y = cycles[0] + (i+1)*segment_size + ryread_offset\n",
    "        stop2y  = cycles[0] + (i+1)*segment_size + ryread_offset + rupdate_cycles\n",
    "    for trace in traces[:attack_traces]:\n",
    "        corr += np.corrcoef(trace.wave[start1:stop1], trace.wave[start2y:stop2y])[0][1]\n",
    "        \n",
    "    corr /= attack_traces # normalize so that decisions thresholds remain constant if we change no_traces\n",
    "    corrs.append(corr)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Guess k one bit at a time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "threshold = initial_threshold\n",
    "guess = ''\n",
    "for kbit in range(255):\n",
    "    if corrs[kbit] > threshold:\n",
    "        guess += '0'\n",
    "    else:\n",
    "        guess += '1'\n",
    "        threshold = regular_threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since our decision metric for bit $i$ calculates correlation with events in processing bit $i+1$, we cannot use it to guess the last bit of $k$.\n",
    "\n",
    "But since there are only two possibilities, we simply check which of the two is correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "guesses = [int(guess + '0', 2), int(guess + '1', 2)]\n",
    "\n",
    "if k in guesses:\n",
    "    print('Guessed right!')\n",
    "else:\n",
    "    print('Attack failed.')\n",
    "    print('Guesses: %s' % hex(guesses[0]))\n",
    "    print('         %s' % hex(guesses[1]))\n",
    "    print('Correct: %s' % hex(k))\n",
    "    wrong_bits = []\n",
    "    for kbit in range(255):\n",
    "        if int(guess[kbit]) != ((k >> (255-kbit)) & 1):\n",
    "            wrong_bits.append(255-kbit)\n",
    "    print('%d wrong bits: %s' % (len(wrong_bits), wrong_bits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Go back and reduce the number of traces used to see how many are required (`attack_traces` variable in the correlation calculation cell).\n",
    "\n",
    "You may see the attack succeed with as few as 8 traces. With the recorded traces, 40 traces are required. What's perhaps surprising is that with just a single trace, a large percentage of the bits are guessed correctly (even with the recorded traces). There are attacks which allow the full k to be recovered from partial knowledge of k (see for example https://link.springer.com/article/10.1023/A:1025436905711), but that's a lot more math-heavy and beyond the scope of this tutorial.\n",
    "\n",
    "Go ahead and repeat the attack for different values of k. Note that k must be nonzero and must be less than the curve order; here is a function to generate a random valid k:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_k(bits=256, tries=100):\n",
    "    import random\n",
    "    for i in range(tries):\n",
    "        k = random.getrandbits(bits)\n",
    "        if k < target.curve.order and k > 0:\n",
    "            return k\n",
    "    raise ValueError(\"Failed to generate a valid random k after %d tries!\" % self.tries)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Epilogue: Black vs White Box\n",
    "\n",
    "This attack was developed and presented as a white-box attack: we looked at the source code, we ran simulations, we extracted points of interest from simulation waveforms. From an educational point of view, this approach allowed us to better show how and why the attack works. It's the best case for offense, and the worst-case for defense.\n",
    "\n",
    "But it begs the question: would an adversary be successful in a black-box scenario? It can be quickly shown that the answer is yes.\n",
    "\n",
    "Intuitively, the periodicity of the raw power trace means the attacker will be able to identify the processing times for each bit of k. These do not need to be precise; they only need to be consistent (i.e. a fixed number of clock cycles offset from what the real times are). This RSA notebook shows an example of how one might do this: [PA_SPA_2-RSA_on_XMEGA_8bit.ipynb](../../archive/PA_SPA_2-RSA_on_XMEGA_8bit.ipynb)\n",
    "\n",
    "With these times in hand, an attack could be as simple as computing the correlation across the different bits of k. The attacker doesn't need to identify exactly when `move_inhibit` is occurring: by computing the correlation over the full bit processing, that event will be included. It is likely that more traces will be required -- how much is left as an exercise to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's Next\n",
    "\n",
    "You could choose to stop here, but hopefully you've found this fascinating enough that you'll carry on to part 2, where we improve the attack and introduces new ways to measure its performance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
